package com.xiaoyu.sort;

import com.xiaoyu.sort.basic.HeapSort;

import java.util.Arrays;

/**
 * @program: DS_and_A
 * @description: 数组中的第K个最大元素:可以使用分治算法或者堆算法(对应是快排和堆排)
 *
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 *
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 *
 * @author: YuWenYi
 * @create: 2021-05-09 09:04
 **/
public class FindKthLargest {

    //解法一:调用API(但是这样毕竟只是取巧)
    public static int findKthLargest1(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }

    //解法二:使用快排的改进版-->快速选择排序
    public int findKthLargest2(int[] nums, int k) {
        quickSelectSort(nums,0,nums.length-1,k);
        return nums[nums.length-k];
    }
    public void quickSelectSort(int[] nums,int left,int right,int k){
        if (left > right){
            return;
        }
        int l = left;
        int r = right;
        int pivot = nums[left];  //取首位作为基准数来切分数组
        int hole = left;   //取pivot的初始位置为首坑位

        while (l < r){
            while (l <r){
                //如果在右边找到了小于pivot的值,那么坑一定在左边
                if (nums[r] < pivot){
                    nums[hole] = nums[r];
                    hole = r;
                    l++;
                    break;
                }
                //如果没找到就继续向左找
                r--;
            }

            while (l < r){
                if (nums[l] > pivot){
                   nums[hole] = nums[l];
                   hole = l;
                   r--;
                   break;
                }
                l++;
            }
        }
        nums[hole] = pivot;

        //如果排序后基准位的位置正好就是我们指定的位置,那么就代表获取到了第K个值了!
        if (hole == nums.length-k)
            return;

        if (hole < nums.length-k){
            quickSelectSort(nums,l+1,right,k);  //如果坑位在我们指定位置的左边,那么就只需要进行右递归
        }else if (hole > nums.length-k){
            quickSelectSort(nums,left,l-1,k);  //如果坑位在我们指定位置的右边,那么只需要进行左递归
        }
    }


    //解法三:使用堆排序的改编版:建立一个大根堆，做 k−1 次"删除"操作后堆顶元素就是我们要找的答案
    public int findKthLargest(int[] nums, int k) {
        HeapSort.build_heap(nums,nums.length);  //构建大顶堆
        for (int i = nums.length - 1; i >= nums.length - k + 1; i--) {
            swap(nums, 0, i);
            HeapSort.heapify(nums,i,0);
        }
        return nums[0];  //返回堆顶元素
    }
    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }



    public static void main(String[] args) {
        FindKthLargest fk = new FindKthLargest();

        int[] nums = new int[]{3,2,3,1,2,4,5,5,6};

        int kthLargest = fk.findKthLargest(nums, 5);

        System.out.println(kthLargest);
    }

}
